6422. Безопасный полет

В настоящее время из-за сокращения бюджета даже шпионы должны использовать коммерческие авиакомпании для путешествия между городами в мире. Хотя этот режим поездок может быть и очень удобным для шпиона, однако также создает проблему: шпион должен доверять пилоту – то есть убедиться, что он не находится в опасности во время полета. И даже хуже: иногда нет прямого рейса между некоторыми парами городов, так что шпион должен лететь несколькими рейсами, чтобы добраться до нужного места, вследствие чего он должен доверять нескольким пилотам!

Для ограничения вопросов доверия Вы обратились за помощью. По имеющемуся расписанию полетов следует найти наименьший набор пилотов, которым следует доверять чтобы шпион мог безопасно путешествовать между всеми городами.

Вход. Первая строка содержит количество тестов, которое не больше 100. Далее для каждого теста:

· в одной строке содержится количество городов n (2 ≤ n ≤ 1000) и пилотов m (1 ≤ m ≤ 10000).

· m строк с числами a и b (1 ≤ a, b ≤ n, a ≠ b): пилот летает между городами a и b туда и обратно.

Путешествовать между городами можно пользуясь одним или несколькими перелетами. Граф является связным.

Выход. Для каждого теста в отдельной строке вывести наименьшее количество пилотов, которым следует доверять шпиону, чтобы иметь возможность путешествовать между любой парой городов.

Пример входа	Пример выхода
2 3 3 1 2 2 3 1 3 5 4 2 1 2 3 4 3 4 5	2 4

РЕШЕНИЕ

конструктив

Анализ алгоритма

Если связный граф содержит n вершин, то любой его остов содержит n – 1 ребро. Чтобы иметь возможность путешествовать между любой парой городов, шпион должен выбрать любой остов графа и доверять n – 1 пилоту.

Реализация алгоритма

Для каждого теста следует вывести ответ – количество вершин, уменьшенное на 1.

scanf("%d", &tests);

while (tests--)

{

scanf("%d %d", &n, &m);

res = n - 1;

for (i = 0; i < m; i++)

scanf("%d %d", &a, &b);

printf("%d\n", res);

}